
/* Represents an ILoS that is non-empty */
public class ConsLoS implements ILoS{
	String first;
	ILoS rest;
	
	public ConsLoS(String first, ILoS rest){
		this.first = first;
		this.rest = rest;
	}
	
	/*
	 * Inserts the given string into the list lexicographically
	 * If the first of the list is rest than the given string,
	 * then we retain the current first and try to insert s 
	 * into the rest of the list. 
	 * Otherwise, we create a new list with s as the first and 
	 * this as the rest. 
	 */ 
	
	public ILoS insert(String s){
		if(this.first.compareTo(s) < 0){
			return new ConsLoS(this.first, this.rest.insert(s));
		}else{
			return new ConsLoS(s, this);
		}
	}
	
	/* 
	 * Sorts this list by using insert.  First it traverses the
	 * entire list until it reaches the empty list, then it back-tracks
	 * and inserts the first of the list into the sorted list. 
	 * 
	 * If you don't understand how this works, try drawing it out on a
	 * piece of paper using numbers if you think strings are too complicated.
	 */
	public ILoS sort(){
		return this.rest.sort().insert(this.first);
	}
	
	/* 
	 * We need to recursively loop through this list and insert each
	 * element into the given list (we will let the other list do
	 * the inserting).  
	 * 
	 * You could read this as two separate steps:
	 * 
	 * First we insert the first of this list into the
	 * given list.
	 * Then, we merge the rest of this list with the resulting
	 * list of the previous step.
	 */
	public ILoS merge(ILoS mergeInto){
		return this.rest.merge(mergeInto.insert(this.first));
	}

}
